什么是动态规划，我们要如何描述它?

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

“状态”用来描述该问题的子问题的解。

递推、递归和迭代

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

通常情况下，迭代俗称“循环”。
编程语言中的for\foreach\while\loop\do while等都是循环

递归与循环：
从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。当递归次数较多时，内存占用也会随之增加。

递推与递归：

从程序上看，递归表现为自己调用自己，递推则没有这样的形式。
递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题。
是逆向的。递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。
递归中，问题的n要求是计算之前就知道的，而递推可以在计算中确定，不要求计算前就知道n。
一般来说，递推的效率高于递归（当然是递推可以计算的情况下）。

动态规划和贪心算法的区别

相同点

动态规划和贪心算法都是一种递推算法。
均有局部最优解来推导全局最优解。

不同点

贪心算法

贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法

全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
边界条件:即最简单的，可以直接得出的局部最优解
贪心算法与动态规划
贪心法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：

不能保证求得的最后解是最佳的；
不能用来求最大或最小解问题；

只能求满足某些约束条件的可行解的范围。实现该算法的过程：
从问题的某一初始解出发；

1
2
3

while   能朝给定总目标前进一步   do   
    求出可行解的一个解元素；   
    由所有解元素组合成问题的一个可行解 。

贪心算法最经典的例子，给钱问题。
比如中国的货币，只看元，有1元2元5元10元20、50、100

如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？
如果用贪心算，就是我每一次拿那张可能拿的最大的。
比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元
也就是3张 10、5、1。

每次拿能拿的最大的，就是贪心。

但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解，而且贪心算法很好想得到。
再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了 :

1
2
3

比如某国的钱币分为   1元3元4元   
如果要拿6元钱   怎么拿？贪心的话   先拿4   再拿两个1     一共3张钱   
实际最优呢？   两张3元就够了。

求最优解的问题，从根本上说是一种对解空间的遍历。最直接的暴力分析容易得到，最优解的解空间通常都是以指数阶增长，因此暴力穷举都是不可行的。
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，如上面的分析，这是不可行的。
贪心和动态规划本质上是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是“子问题最优性”。即，组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的。如果以自顶向下的方向看问题树（原问题作根），则，我们每次只需要向下遍历代表最优解的子树就可以保证会得到整体的最优解。形象一点说，可以简单的用一个值（最优值）代表整个子树，而不用去求出这个子树所可能代表的所有值。
动态规划方法代表了这一类问题的一般解法。我们自底向上（从叶子向根）构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。动态规划的代价就取决于可选择的数目（树的叉数）和子问题的的数目（树的节点数，或者是树的高度？）。
贪心算法是动态规划方法的一个特例。贪心特在，可以证明，每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。

动态规划：从新手到专家

意识到，DP是由上一个状态解找到下个状态解，所以一般要去找上一个状态，如-1，j等等。

问题一

一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS：longest increasing subsequence)

状态：d[i]表示i长度的序列最长非降子序列的长度。
状态转移方程：d[i] = max{1, d[j] + 1},其中j < i, A[j] <= A[i]。

问题二

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)

状态：d[i]表示凑够i元的最少硬币个数
状态转移方程：d[i] = min{d[i - vj] + 1 }，其中i - vj >= 0，vj表示第j个硬币的面值;

问题三

无向图G有N个结点(1<N<=1000)及一些边，每一条边上带有正的权重值。找到结点1到结点N的最短路径，或者输出不存在这样的路径。

提示：在每一步中，对于那些没有计算过的结点，及那些已经计算出从结点1到它的最短路径的结点，如果它们间有边，则计算从结点1到未计算结点的最短路径。

状态：d[i]表示结点1到达结点i的最短路径长度。
状态转移方程：d[i] = min{d[i], d[j] + dis[i][j]}。2-N的结点初始长度为无穷，每次判断一个结点的邻居。

问题四

平面上有N＊M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。

状态：d[i][j]表示在格子(i, j)最多能收集到的苹果数量。
状态转移方程：d[i][j] = max{d[i-1][j] (if i > 0), d[i][j - 1] (if j > 0)} + A[i][j]。

问题五(带有额外条件的DP问题)

无向图G有N个结点，它的边上带有正的权重值。你从结点1开始走，并且一开始的时候你身上带有M元钱。如果你经过结点i，那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱，就不能从那个结点经过。在这样的限制条件下，找到从结点1到结点N的最短路径。或者输出该路径不存在。如果存在多条最短路径，那么输出花钱数量最少的那条。限制：1<N<=100 ; 0<=M<=100 ; 对于每个i，0<=S[i]<=100；正如我们所看到的，如果没有额外的限制条件(在结点处要收费，费用不足还不给过)

状态：d[i][j]表示从开始结点到结点i的最短路径长度，且剩余j元。
For All Neighbors p of Vertex k:
状态转移方程(参考问题三)：d[p][j - s[p]] = min{d[i][j] + dis[i][p], d[p][j - s[p]]} (if j - s[p] >= 0能够支付费用)

问题六(高级)

给定一个M行N列的矩阵(M*N个格子)，每个格子中放着一定数量的苹果。你从左上角的格子开始，只能向下或向右走，目的地是右下角的格子。你每走过一个格子，就把格子上的苹果都收集起来。然后你从右下角走回左上角的格子，每次只能向左或是向上走，同样的，走过一个格子就把里面的苹果都收集起来。最后，你再一次从左上角走到右下角，每过一个格子同样要收集起里面的苹果 (如果格子里的苹果数为0，就不用收集)。求你最多能收集到多少苹果。

注意：当你经过一个格子时，你要一次性把格子里的苹果都拿走。

限制条件：1 < N, M <= 50；每个格子里的苹果数量是0到1000(包含0和1000)。

我们可以将这3条路径记为左，中，右路径。对于两条相交路径(如下图)：

在不影响结果的情况下，我们可以将它们视为两条不相交的路径：

这样一来，我们将得到左，中，右3条路径。此外，如果我们要得到最优解，路径之间不能相交(除了左上角和右下角必然会相交的格子)。因此对于每一行y( 除了第一行和最后一行)，三条路径对应的x坐标要满足：x1[y] < x2[y] < x3[y]。经过这一步的分析，问题的DP解法就进一步地清晰了。让我们考虑行y，对于每一个x1[y-1]，x2[y-1]和x3[y-1]，我们已经找到了能收集到最多苹果数量的路径。根据它们，我们能求出行y的最优解。现在我们要做的就是找到从一行移动到下一行的方式。令Max[i][j][k]表示到第y-1行为止收集到苹果的最大数量，其中3条路径分别止于第i,j,k列。对于下一行y，对每个Max[i][j][k] 都加上格子(y,i)，(y,j)和(y,k)内的苹果数量。因此，每一步我们都向下移动。我们做了这一步移动之后，还要考虑到，一条路径是有可能向右移动的。 (对于每一个格子，我们有可能是从它上面向下移动到它，也可能是从它左边向右移动到它)。为了保证3条路径互不相交，我们首先要考虑左边的路径向右移动的情况，然后是中间，最后是右边的路径。为了更好的理解，让我们来考虑左边的路径向右移动的情况，对于每一个可能的j,k对(j < k)，对每个i(i < j)，考虑从位置(i-1,j,k)移动到位置(i,j,k)。处理完左边的路径，再处理中间的路径，最后处理右边的路径。方法都差不多。

问题七

What is possibility of rolling N dice and the sum of the numbers equals to M?

先想想仍N次骰子，所有的骰子和为M的组合方式数量。
状态：d[i][j]表示仍i次骰子的和为j的组合方式数量。
状态转移方程：d[i][j] = d[i - 1][j - v] + d[i][j]。v表示骰子的数1-6。

根据上面的方式则求出：p = d[N][M] / 6^N。
N次幂数值太大，做题尽量避免指数。

状态：d[i][j]表示仍i次骰子的和为j的概率。
状态转移方程：d[i][j] = d[i][j] + d[i - 1][j - v] * (1/6)。v表示骰子的数1-6，乘上最后一次扔v的概率1/6，注意要把最后的6种情况加起来，因为最后一步有6种可能都能加起来得到M，几种概率是并行的，所以求和。

动态规划